package club.xiaojiawei.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/23/22 10:44 AM
 * @question 673. 最长递增子序列的个数
 * @description 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 * 注意 这个数列必须是 严格 递增的。
 */
public class FindNumberOfLIS673 {

    public static void main(String[] args) {
        FindNumberOfLIS673 test = new FindNumberOfLIS673();
        int result = test.findNumberOfLIS4(new int[]{1,3,5,4,3,1,4,5,1,3,5,4,3});
        System.out.println(result);
    }

    /**
     * 官方-dp
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n^2)
     * @param nums
     * @return
     */
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0, ans = 0;
        //        dp[i] = n 表示以下标i处的元素作为子序列里的最后一个元素时的最长子序列为n
        int[] dp = new int[n];
//        cnt[i] = n 表示数量为n
        int[] cnt = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j]; // 重置计数
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }

    /**
     * 官方-贪心 + 前缀和 + 二分查找
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     * @param nums
     * @return
     */
    public int findNumberOfLIS2(int[] nums) {
//        d[i] 表示子序列长度为i的情况，d[i]处的数组是递减的，是使用贪心算法依次填入更小的值为结尾
        var d = new ArrayList<List<Integer>>();
//        cnt[i]处的数组表示子序列长度为i的情况下对应的子序列数量为多少，且存储的是前缀和
        var cnt = new ArrayList<List<Integer>>();
        for (int v : nums) {
//            查找v应该插入到的长度处
            int i = binarySearch1(d.size(), d, v);
//            满足要求的子序列数量
            int c = 1;
//            大于0的目的：防止数组越界
            if (i > 0) {
//                查找v应该插入到d[i]处数组的位置
                int k = binarySearch2(d.get(i - 1).size(), d.get(i - 1), v);
//                因为d[i]是递减的，且cnt[i]存储的是前缀和，所以把cnt[i - 1]处的全部子序列数量减去v插入下标处的子序列数量
                c = cnt.get(i - 1).get(cnt.get(i - 1).size() - 1) - cnt.get(i - 1).get(k);
            }
//            i == d.size()表示没有对应的长度，直接插入到现有最大长度+1处
            if (i == d.size()) {
                var dList = new ArrayList<Integer>();
                dList.add(v);
                d.add(dList);
                var cntList = new ArrayList<Integer>();
//                添加的0的目的：防止数组越界
                cntList.add(0);
                cntList.add(c);
                cnt.add(cntList);
            } else {
                d.get(i).add(v);
                int cntSize = cnt.get(i).size();
//                因为存储的是前缀和，所以要把前面的一并加上，即cnt.get(i).get(cntSize - 1) + c
                cnt.get(i).add(cnt.get(i).get(cntSize - 1) + c);
            }
        }
        int size1 = cnt.size(), size2 = cnt.get(size1 - 1).size();
        return cnt.get(size1 - 1).get(size2 - 1);
    }

    /**
     * 二分查找（递增序列）
     * @param n
     * @param d
     * @param target
     * @return
     */
    public int binarySearch1(int n, List<List<Integer>> d, int target) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            List<Integer> list = d.get(mid);
            if (list.get(list.size() - 1) >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    /**
     * 二分查找（递减序列）
     * @param n
     * @param list
     * @param target
     * @return
     */
    public int binarySearch2(int n, List<Integer> list, int target) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (list.get(mid) < target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    /**
     * 民间-贪心 + 前缀和 + 二分查找
     * @param nums
     * @return
     */
    public int findNumberOfLIS3(int[] nums) {
        int len = nums.length;
        List<List<Integer>> dp = new ArrayList<>();
        List<List<Integer>> cnt = new ArrayList<>();
        int[] minArr = new int[len + 1];
        minArr[0] = Integer.MIN_VALUE;
        int minArrIndex = 0;
        for (int cur : nums) {
            if (cur > minArr[minArrIndex]) {
                minArr[++minArrIndex] = cur;
                add(dp, cnt, cur);
            } else {
                int index = Arrays.binarySearch(minArr, 0, minArrIndex + 1, cur);
                if (index < 0) {
                    index = -index - 1;
                }
                minArr[index] = cur;
                update(dp, cnt, index - 1, cur);
            }
        }
        List<Integer> maxList = cnt.get(cnt.size() - 1);
        return maxList.get(maxList.size() - 1);
    }
    public void add(List<List<Integer>> dp, List<List<Integer>> cnt, int target) {
        dp.add(new ArrayList<>());
        List<Integer> newList = new ArrayList<>();
        newList.add(0);
        cnt.add(newList);
        update(dp, cnt, cnt.size() - 1, target);
    }
    public void update(List<List<Integer>> dp, List<List<Integer>> cnt, int index, int target) {
        List<Integer> curCnt = cnt.get(index);
        List<Integer> curDp = dp.get(index);
        curDp.add(target);
        int addCnt = index == 0 ? 1 : getCnt(dp, cnt, index - 1, target);
        curCnt.add(curCnt.get(curCnt.size() - 1) + addCnt);
    }
    public int getCnt(List<List<Integer>> dp, List<List<Integer>> cnt, int index, int target) {
        int findIndex = binarySearch(dp.get(index), target);
        List<Integer> curCnt = cnt.get(index);
        return curCnt.get(curCnt.size() - 1) - curCnt.get(findIndex);
    }
    public int binarySearch(List<Integer> curDp, int target) {
        int l = 0, r = curDp.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            int curVal = curDp.get(mid);
            if (curVal >= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    static class Value{
        int length;
        int count;
        public Value(int len, int ct) {
            length=len;
            count=ct;
        }
    }
    static class Node {
        Value val;
        Node left, right;
        int rangeLeft, rangeRight;
        public Node(int start, int end) {
            left=null;
            right=null;
            rangeLeft =start;
            rangeRight =end;
            val = new Value(0,1);
        }
        public int getRangeMid() {
            return rangeLeft +(rangeRight - rangeLeft)/2;
        }
        public Node getLeft() {
            if(left==null)
                left=new Node(rangeLeft,getRangeMid());
            return left;
        }
        public Node getRight() {
            if(right==null)
                right=new Node(getRangeMid()+1, rangeRight);
            return right;
        }
    }

    /**
     * 民间-线段树
     * @param nums
     * @return
     */
    public int findNumberOfLIS4(int[] nums) {
        if(nums.length <= 1) {
            return nums.length;
        }
        int min = nums[0], max = nums[0];
        for(int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        Node root = new Node(min, max);
        for(int num : nums) {
            Value v = query(root, num - 1);
            insert(root, num, new Value(v.length+1, v.count));
        }
        return root.val.count;
    }

    public Value query(Node root, int key) {
        if(root.rangeRight <= key) {
            return root.val;
        }else if(root.rangeLeft > key) {
            return new Value(0, 1);
        }else {
            return merge(query(root.getLeft(), key), query(root.getRight(), key));
        }
    }

    public Value merge(Value v1,Value v2) {
        if(v1.length == v2.length) {
            if(v1.length == 0) {
                return new Value(0, 1);
            }
            return new Value(v1.length, v1.count + v2.count);
        }
        return v1.length > v2.length? v1 : v2;
    }

    public void insert(Node root, int key, Value val) {
        if(root.rangeLeft == root.rangeRight) {
            root.val = merge(val, root.val);
            return;
        }else if(key <= root.getRangeMid())
            insert(root.getLeft(), key, val);
        else{
            insert(root.getRight(), key, val);
        }
        root.val = merge(root.getLeft().val, root.getRight().val);
    }
}
